home *** CD-ROM | disk | FTP | other *** search
/ La Traviata / La Traviata.iso / viewer / gif_csrc.zip / DECODER.C next >
C/C++ Source or Header  |  1990-10-05  |  12KB  |  376 lines
  1. /* DECODE.C - An LZW decoder for GIF
  2.  * Copyright (C) 1987, by Steven A. Bennett
  3.  *
  4.  * Permission is given by the author to freely redistribute and include
  5.  * this code in any program as long as this credit is given where due.
  6.  *
  7.  * In accordance with the above, I want to credit Steve Wilhite who wrote
  8.  * the code which this is heavily inspired by...
  9.  *
  10.  * GIF and 'Graphics Interchange Format' are trademarks (tm) of
  11.  * Compuserve, Incorporated, an H&R Block Company.
  12.  *
  13.  * Release Notes: This file contains a decoder routine for GIF images
  14.  * which is similar, structurally, to the original routine by Steve Wilhite.
  15.  * It is, however, somewhat noticably faster in most cases.
  16.  *
  17.  */
  18.  
  19. #include "std.h"
  20. #include "errs.h"
  21.  
  22. IMPORT TEXT *malloc();                 /* Standard C library allocation */
  23.  
  24. /* IMPORT INT get_byte()
  25.  *
  26.  *   - This external (machine specific) function is expected to return
  27.  * either the next byte from the GIF file, or a negative number, as
  28.  * defined in ERRS.H.
  29.  */
  30. IMPORT INT get_byte();
  31.  
  32. /* IMPORT INT out_line(pixels, linelen)
  33.  *     UBYTE pixels[];
  34.  *     INT linelen;
  35.  *
  36.  *   - This function takes a full line of pixels (one byte per pixel) and
  37.  * displays them (or does whatever your program wants with them...).  It
  38.  * should return zero, or negative if an error or some other event occurs
  39.  * which would require aborting the decode process...  Note that the length
  40.  * passed will almost always be equal to the line length passed to the
  41.  * decoder function, with the sole exception occurring when an ending code
  42.  * occurs in an odd place in the GIF file...  In any case, linelen will be
  43.  * equal to the number of pixels passed...
  44.  */
  45. IMPORT INT out_line();
  46.  
  47. /* IMPORT INT bad_code_count;
  48.  *
  49.  * This value is the only other global required by the using program, and
  50.  * is incremented each time an out of range code is read by the decoder.
  51.  * When this value is non-zero after a decode, your GIF file is probably
  52.  * corrupt in some way...
  53.  */
  54. IMPORT INT bad_code_count;
  55.  
  56. #define NULL   0L
  57. #define MAX_CODES   4095
  58.  
  59. /* Static variables */
  60. LOCAL WORD curr_size;                     /* The current code size */
  61. LOCAL WORD clear;                         /* Value for a clear code */
  62. LOCAL WORD ending;                        /* Value for a ending code */
  63. LOCAL WORD newcodes;                      /* First available code */
  64. LOCAL WORD top_slot;                      /* Highest code for current size */
  65. LOCAL WORD slot;                          /* Last read code */
  66.  
  67. /* The following static variables are used
  68.  * for seperating out codes
  69.  */
  70. LOCAL WORD navail_bytes = 0;              /* # bytes left in block */
  71. LOCAL WORD nbits_left = 0;                /* # bits left in current byte */
  72. LOCAL UTINY b1;                           /* Current byte */
  73. LOCAL UTINY byte_buff[257];               /* Current block */
  74. LOCAL UTINY *pbytes;                      /* Pointer to next byte in block */
  75.  
  76. LOCAL LONG code_mask[13] = {
  77.      0,
  78.      0x0001, 0x0003,
  79.      0x0007, 0x000F,
  80.      0x001F, 0x003F,
  81.      0x007F, 0x00FF,
  82.      0x01FF, 0x03FF,
  83.      0x07FF, 0x0FFF
  84.      };
  85.  
  86.  
  87. /* This function initializes the decoder for reading a new image.
  88.  */
  89. LOCAL WORD init_exp(size)
  90.    WORD size;
  91.    {
  92.    curr_size = size + 1;
  93.    top_slot = 1 << curr_size;
  94.    clear = 1 << size;
  95.    ending = clear + 1;
  96.    slot = newcodes = ending + 1;
  97.    navail_bytes = nbits_left = 0;
  98.    return(0);
  99.    }
  100.  
  101. /* get_next_code()
  102.  * - gets the next code from the GIF file.  Returns the code, or else
  103.  * a negative number in case of file errors...
  104.  */
  105. LOCAL WORD get_next_code()
  106.    {
  107.    WORD i, x;
  108.    ULONG ret;
  109.  
  110.    if (nbits_left == 0)
  111.       {
  112.       if (navail_bytes <= 0)
  113.          {
  114.  
  115.          /* Out of bytes in current block, so read next block
  116.           */
  117.          pbytes = byte_buff;
  118.          if ((navail_bytes = get_byte()) < 0)
  119.             return(navail_bytes);
  120.          else if (navail_bytes)
  121.             {
  122.             for (i = 0; i < navail_bytes; ++i)
  123.                {
  124.                if ((x = get_byte()) < 0)
  125.                   return(x);
  126.                byte_buff[i] = x;
  127.                }
  128.             }
  129.          }
  130.       b1 = *pbytes++;
  131.       nbits_left = 8;
  132.       --navail_bytes;
  133.       }
  134.  
  135.    ret = b1 >> (8 - nbits_left);
  136.    while (curr_size > nbits_left)
  137.       {
  138.       if (navail_bytes <= 0)
  139.          {
  140.  
  141.          /* Out of bytes in current block, so read next block
  142.           */
  143.          pbytes = byte_buff;
  144.          if ((navail_bytes = get_byte()) < 0)
  145.             return(navail_bytes);
  146.          else if (navail_bytes)
  147.             {
  148.             for (i = 0; i < navail_bytes; ++i)
  149.                {
  150.                if ((x = get_byte()) < 0)
  151.                   return(x);
  152.                byte_buff[i] = x;
  153.                }
  154.             }
  155.          }
  156.       b1 = *pbytes++;
  157.       ret |= b1 << nbits_left;
  158.       nbits_left += 8;
  159.       --navail_bytes;
  160.       }
  161.    nbits_left -= curr_size;
  162.    ret &= code_mask[curr_size];
  163.    return((WORD)(ret));
  164.    }
  165.  
  166.  
  167. /* The reason we have these seperated like this instead of using
  168.  * a structure like the original Wilhite code did, is because this
  169.  * stuff generally produces significantly faster code when compiled...
  170.  * This code is full of similar speedups...  (For a good book on writing
  171.  * C for speed or for space optomisation, see Efficient C by Tom Plum,
  172.  * published by Plum-Hall Associates...)
  173.  */
  174. LOCAL UTINY stack[MAX_CODES + 1];            /* Stack for storing pixels */
  175. LOCAL UTINY suffix[MAX_CODES + 1];           /* Suffix table */
  176. LOCAL UWORD prefix[MAX_CODES + 1];           /* Prefix linked list */
  177.  
  178. /* WORD decoder(linewidth)
  179.  *    WORD linewidth;               * Pixels per line of image *
  180.  *
  181.  * - This function decodes an LZW image, according to the method used
  182.  * in the GIF spec.  Every *linewidth* "characters" (ie. pixels) decoded
  183.  * will generate a call to out_line(), which is a user specific function
  184.  * to display a line of pixels.  The function gets it's codes from
  185.  * get_next_code() which is responsible for reading blocks of data and
  186.  * seperating them into the proper size codes.  Finally, get_byte() is
  187.  * the global routine to read the next byte from the GIF file.
  188.  *
  189.  * It is generally a good idea to have linewidth correspond to the actual
  190.  * width of a line (as specified in the Image header) to make your own
  191.  * code a bit simpler, but it isn't absolutely necessary.
  192.  *
  193.  * Returns: 0 if successful, else negative.  (See ERRS.H)
  194.  *
  195.  */
  196.  
  197. WORD decoder(linewidth)
  198.    WORD linewidth;
  199.    {
  200.    FAST UTINY *sp, *bufptr;
  201.    UTINY *buf;
  202.    FAST WORD code, fc, oc, bufcnt;
  203.    WORD c, size, ret;
  204.  
  205.    /* Initialize for decoding a new image...
  206.     */
  207.    if ((size = get_byte()) < 0)
  208.       return(size);
  209.    if (size < 2 || 9 < size)
  210.       return(BAD_CODE_SIZE);
  211.    init_exp(size);
  212.  
  213.    /* Initialize in case they forgot to put in a clear code.
  214.     * (This shouldn't happen, but we'll try and decode it anyway...)
  215.     */
  216.    oc = fc = 0;
  217.  
  218.    /* Allocate space for the decode buffer
  219.     */
  220.    if ((buf = (UTINY *)malloc(linewidth + 1)) == NULL)
  221.       return(OUT_OF_MEMORY);
  222.  
  223.    /* Set up the stack pointer and decode buffer pointer
  224.     */
  225.    sp = stack;
  226.    bufptr = buf;
  227.    bufcnt = linewidth;
  228.  
  229.    /* This is the main loop.  For each code we get we pass through the
  230.     * linked list of prefix codes, pushing the corresponding "character" for
  231.     * each code onto the stack.  When the list reaches a single "character"
  232.     * we push that on the stack too, and then start unstacking each
  233.     * character for output in the correct order.  Special handling is
  234.     * included for the clear code, and the whole thing ends when we get
  235.     * an ending code.
  236.     */
  237.    while ((c = get_next_code()) != ending)
  238.       {
  239.  
  240.       /* If we had a file error, return without completing the decode
  241.        */
  242.       if (c < 0)
  243.          {
  244.          free(buf);
  245.          return(0);
  246.          }
  247.  
  248.       /* If the code is a clear code, reinitialize all necessary items.
  249.        */
  250.       if (c == clear)
  251.          {
  252.          curr_size = size + 1;
  253.          slot = newcodes;
  254.          top_slot = 1 << curr_size;
  255.  
  256.          /* Continue reading codes until we get a non-clear code
  257.           * (Another unlikely, but possible case...)
  258.           */
  259.          while ((c = get_next_code()) == clear)
  260.             ;
  261.  
  262.          /* If we get an ending code immediately after a clear code
  263.           * (Yet another unlikely case), then break out of the loop.
  264.           */
  265.          if (c == ending)
  266.             break;
  267.  
  268.          /* Finally, if the code is beyond the range of already set codes,
  269.           * (This one had better NOT happen...  I have no idea what will
  270.           * result from this, but I doubt it will look good...) then set it
  271.           * to color zero.
  272.           */
  273.          if (c >= slot)
  274.             c = 0;
  275.  
  276.          oc = fc = c;
  277.  
  278.          /* And let us not forget to put the char into the buffer... And
  279.           * if, on the off chance, we were exactly one pixel from the end
  280.           * of the line, we have to send the buffer to the out_line()
  281.           * routine...
  282.           */
  283.          *bufptr++ = c;
  284.          if (--bufcnt == 0)
  285.             {
  286.             if ((ret = out_line(buf, linewidth)) < 0)
  287.                {
  288.                free(buf);
  289.                return(ret);
  290.                }
  291.             bufptr = buf;
  292.             bufcnt = linewidth;
  293.             }
  294.          }
  295.       else
  296.          {
  297.  
  298.          /* In this case, it's not a clear code or an ending code, so
  299.           * it must be a code code...  So we can now decode the code into
  300.           * a stack of character codes. (Clear as mud, right?)
  301.           */
  302.          code = c;
  303.  
  304.          /* Here we go again with one of those off chances...  If, on the
  305.           * off chance, the code we got is beyond the range of those already
  306.           * set up (Another thing which had better NOT happen...) we trick
  307.           * the decoder into thinking it actually got the last code read.
  308.           * (Hmmn... I'm not sure why this works...  But it does...)
  309.           */
  310.          if (code >= slot)
  311.             {
  312.             if (code > slot)
  313.                ++bad_code_count;
  314.             code = oc;
  315.             *sp++ = fc;
  316.             }
  317.  
  318.          /* Here we scan back along the linked list of prefixes, pushing
  319.           * helpless characters (ie. suffixes) onto the stack as we do so.
  320.           */
  321.          while (code >= newcodes)
  322.             {
  323.             *sp++ = suffix[code];
  324.             code = prefix[code];
  325.             }
  326.  
  327.          /* Push the last character on the stack, and set up the new
  328.           * prefix and suffix, and if the required slot number is greater
  329.           * than that allowed by the current bit size, increase the bit
  330.           * size.  (NOTE - If we are all full, we *don't* save the new
  331.           * suffix and prefix...  I'm not certain if this is correct...
  332.           * it might be more proper to overwrite the last code...
  333.           */
  334.          *sp++ = code;
  335.          if (slot < top_slot)
  336.             {
  337.             suffix[slot] = fc = code;
  338.             prefix[slot++] = oc;
  339.             oc = c;
  340.             }
  341.          if (slot >= top_slot)
  342.             if (curr_size < 12)
  343.                {
  344.                top_slot <<= 1;
  345.                ++curr_size;
  346.                } 
  347.  
  348.          /* Now that we've pushed the decoded string (in reverse order)
  349.           * onto the stack, lets pop it off and put it into our decode
  350.           * buffer...  And when the decode buffer is full, write another
  351.           * line...
  352.           */
  353.          while (sp > stack)
  354.             {
  355.             *bufptr++ = *(--sp);
  356.             if (--bufcnt == 0)
  357.                {
  358.                if ((ret = out_line(buf, linewidth)) < 0)
  359.                   {
  360.                   free(buf);
  361.                   return(ret);
  362.                   }
  363.                bufptr = buf;
  364.                bufcnt = linewidth;
  365.                }
  366.             }
  367.          }
  368.       }
  369.    ret = 0;
  370.    if (bufcnt != linewidth)
  371.       ret = out_line(buf, (linewidth - bufcnt));
  372.    free(buf);
  373.    return(ret);
  374.    }
  375.  
  376.